package leetcode.editor.cn.dsa26_unionfind;
//给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
// 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
// 此外，你可以假设该网格的四条边均被水包围。
//
// 示例 1：
//输入：grid = [
//  ["1","1","1","1","0"],
//  ["1","1","0","1","0"],
//  ["1","1","0","0","0"],
//  ["0","0","0","0","0"]
//]
//输出：1
//
// 示例 2： 
//输入：grid = [
//  ["1","1","0","0","0"],
//  ["1","1","0","0","0"],
//  ["0","0","1","0","0"],
//  ["0","0","0","1","1"]
//]
//输出：3
//
// 提示： 
// m == grid.length
// n == grid[i].length 
// 1 <= m, n <= 300 
// grid[i][j] 的值为 '0' 或 '1' 
// 
// Related Topics 深度优先搜索 广度优先搜索 并查集 
// 👍 928 👎 0

import java.util.LinkedList;
import java.util.Queue;

public class NumberOfIslands200_1 {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 深度优先搜索
         * @param grid
         * @return
         */
        int m, n;
        public int numIslands(char[][] grid) {
            // 二维网格的长和宽
            m = grid.length;
            n = grid[0].length;
            int res = 0;
            // 1.遍历二维网格，查找每个陆地（1）节点
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == '1') { // 陆地节点
                        // 2.使用深度优先搜索扩展每个连通的陆地节点
                        dfs(grid, i, j);
                        // 4.每完成一次深度优先搜索，岛屿数量加 1
                        res++;
                    }
                }
            }
            return res;
        }
        // 把和[x,y]相连的陆地全部标记为水
        private void dfs(char[][] grid, int x, int y) {
            // 过滤越界情况和“水”节点
            if (x < 0 || y < 0 || x >= m || y >= n
                    || grid[x][y] == '0') return;
            // 3.每扩展一次，将该陆地标记为“水”
            grid[x][y] = '0';
            dfs(grid, x - 1, y); // 扩展当前节点的上邻接点
            dfs(grid, x + 1, y); // 扩展当前节点的下邻接点
            dfs(grid, x, y - 1); // 扩展当前节点的左邻接点
            dfs(grid, x, y + 1);// 扩展当前节点的右邻接点
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}